package com.example.linked;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
 *  构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random
 * 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
 *  例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
 *  返回复制链表的头节点。
 *  用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
 *  val：一个表示 Node.val 的整数。
 *  random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
 *
 *
 *  你的代码 只 接受原链表的头节点 head 作为传入参数。
 *
 *  示例 1：
 * 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
 * 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
 *
 *  示例 2：
 * 输入：head = [[1,1],[2,1]]
 * 输出：[[1,1],[2,1]]
 *
 *  示例 3：
 * 输入：head = [[3,null],[3,0],[3,null]]
 * 输出：[[3,null],[3,0],[3,null]]
 *
 *  示例 4：
 * 输入：head = []
 * 输出：[]
 * 解释：给定的链表为空（空指针），因此返回 null。
 */
public class Leetcode138_CopyRandomList {
    public static void main(String[] args) {
        // [[7,null],[13,0],[11,4],[10,2],[1,0]]
        Node head = new Node(7);
        head.next = new Node(13);
        head.next.next = new Node(11);
        head.next.next.next = new Node(10);
        head.next.next.next.next = new Node(1);

        head.random = null;
        head.next.random = head;
        head.next.next.random = head.next.next.next.next;
        head.next.next.next.random = head.next.next;
        head.next.next.next.next.random = head;

        Node tmp = head;
        while (tmp != null) {
            System.out.println(tmp);
            tmp = tmp.next;
        }

        Node res = new Solution().copyRandomList(head);
        System.out.println("===============");

        tmp = res;
        while (tmp != null) {
            System.out.println(tmp);
            tmp = tmp.next;
        }
    }

    static class Solution {
        /**
         * 优化掉hashMap的空间
         * @param head
         * @return
         */
        private Node copyRandomList4(Node head) {
            if (head == null) return null;
            Node tmp = head;
            // 第一次遍历:将每个节点的复制节点挂在当前节点后面
            // 原链表 A -> B -> C -> D
            // 操作后 A -> A' -> B -> B' -> C -> C' -> D -> D'
            while (tmp != null) {
                Node newNode = new Node(tmp.val);
                newNode.next = tmp.next;
                tmp.next = newNode;
                tmp = tmp.next.next;
            }

            // 第二次遍历修改每个新节点的random指针的指向
            // 原节点的random不指向null时 新节点的random指向为: 当前节点的 random 的 next的节点(即 tmp.random.next)
            tmp = head;
            while (tmp != null) {
                Node newNode = tmp.next;
                newNode.random = (tmp.random != null) ? tmp.random.next : null;
                tmp = tmp.next.next;
            }

            // 改变每个新元素的next指针将新元素形成新链表
            Node newHead = head.next;
            tmp = head;
            while (tmp != null) {
                Node newNode = tmp.next;
                tmp.next = tmp.next.next;
                newNode.next = newNode.next != null ? newNode.next.next : null;
                tmp = tmp.next;
            }

            return newHead;
        }

        /**
         * hashMap(迭代实现)
         * @param head
         * @return
         */
        private Node copyRandomList3(Node head) {
            if (head == null) return null;
            Map<Node, Node> map = new HashMap<>();
            // 首先将每个节点都单独进行拷贝
            Node tmp = head;
            while (tmp != null) {
                map.put(tmp, new Node(tmp.val));
               tmp = tmp.next;
            }

            // 修改每个新节点的 next 和 random 指针
            tmp = head;
            while (tmp != null) {
                Node tmpNew = map.get(tmp);
                tmpNew.next = map.get(tmp.next);
                tmpNew.random = map.get(tmp.random);
                tmp = tmp.next;
            }

            return map.get(head);
        }

        /**
         * 解法二:回溯 + hashmap
         * @param head
         * @return
         */
        Map<Node, Node> cachedMap = new HashMap<>(); // key 原链表的节点, value复制后对应的新节点
        private Node copyRandomList2(Node head) {
            if (head == null) return null;
            if (!cachedMap.containsKey(head)) { // 当前节点没被拷贝才进行拷贝
                Node newHead = new Node(head.val); // 拷贝当前节点
                cachedMap.put(head, newHead);
                newHead.next = copyRandomList2(head.next); // 拷贝节点的next节点
                newHead.random = copyRandomList2(head.random);// 拷贝节点的random节点
            }
            return cachedMap.get(head);
        }

        /**
         * 解法一:hash表
         *
         * @param head
         * @return
         */
        private Node copyRandomList1(Node head) {
            if (head == null) return null;
            Node newHead = new Node(-1), tmpOld = head, tmpNew = newHead;
            Map<Integer, Node> nodeMap = new HashMap<>(); // key为节点的索引, value为对应的节点
            List<Integer> randomIndexList = new ArrayList<>();// 每个旧节点的 random指向的节点在原链表的倒数第几位
            int size = 0;
            // 第一次遍历复制链表(不理会random的指向)
            while (tmpOld != null) {
                tmpNew.next = new Node(tmpOld.val);
                tmpNew = tmpNew.next;
                nodeMap.put(size++, tmpNew); // 将节点和其索引放入hashmap中方便后面直接查找
                int randomCount = 0; // 原链表的random指向null则为0
                if (tmpOld.random != null) {
                    Node randomTmp = tmpOld.random;
                    while (randomTmp != null) {
                        randomCount++;
                        randomTmp = randomTmp.next;
                    }
                }
                randomIndexList.add(randomCount);
                tmpOld = tmpOld.next;
            }

            // 根据nodeMap和各个random节点在原链表的倒数位置确定每个节点的random的指向
            int i = 0;
            tmpNew = newHead.next;
            while (tmpNew != null) {
                int randomPos = randomIndexList.get(i++);
                if (randomPos != 0) {
                    tmpNew.random = nodeMap.get(size - randomPos);
                }
                tmpNew = tmpNew.next;
            }

            return newHead.next;
        }

        public Node copyRandomList(Node head) {
            return copyRandomList4(head);
        }

        /**
         * 普通链表的拷贝(递归实现)
         * @param head
         * @return
         */
        private Node copyList(Node head) {
            if (head == null) return null;
            Node newHead = new Node(head.val);
            newHead.next = copyList(head.next);
            return newHead;
        }
    }

    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "val=" + val +
                    ", next=" + (next == null ? null : next.val) +
                    ", random=" + (random == null ? null : random.val) +
                    '}';
        }
    }
}
